package leetcode_jz_offer.day5_research_array;

/**
 * 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 * 给你一个可能存在重复元素值的数组numbers，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。
 * 链接：https://leetcode.cn/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
 **/
public class Num11_旋转数组的最小数字 {
    //旋转数组左右两半一定都分别仍旧是升序数组，并且左半边大于右半边的值
    //可能存在重复元素说明数组是非降序数组，要注意
    //二分法 mid大于最左边，mid是左边的升序序列的，最小值在右边，更新left=mid继续判断
    //mid小于最左边，mid属于右半边升序序列，最小值在左边，right=mid继续判断
    //当left与right相邻时一定判断完毕，右边的right就是最小值
    //注意arr[left]==arr[right]==arr[mid]时的情况，此时无法判断大小，需要单拎出来判断，从左到右遍历，碰到第一个小于这个值的就是最后结果，全相等结果就是mid
    public static int minArray(int[] numbers) {
        if(numbers==null||numbers.length==0){
            //数组为null或没有内容
            return 0;
        }
        int left=0;
        int right=numbers.length-1;
        int mid=0;
        while (numbers[left]>=numbers[right]){//保证不越界，左边值始终大于右边。其实用left<right也可以
            if(right-1==left){
                //相邻，说明遍历到最后了，右边的一定是小的
                mid=right;
                break;
            }
            //判断是否左中右相等
            mid=left+((right-left)>>1);
            if(numbers[left]==numbers[mid]&&numbers[mid]==numbers[right]){
                for (int i = left; i <right ; i++) {
                    if(numbers[i]>numbers[i+1]){
                        return numbers[i+1];
                    }
                }
                return numbers[mid];
            }
            //左中右一定不同时相等

            if(numbers[mid]>=numbers[left]){//中间值大于左边
                left=mid;
            }else {
                right=mid;
            }
        }
        return numbers[mid];
    }

    public static void main(String[] args) {
        int[] arr={1};
        int a=minArray(arr);
        System.out.println(a);
    }
}
